package LeetCode.leetcode;

import domain.ListNode;

/**
 * 相交链表
 *
 * @author: leiwenkang02@meituan.com
 * @date: 2018/8/8
 * @time: 19:28
 */
public class Test160相交链表 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        //计算A链表的长度
        ListNode p1 = headA;
        int length1 = 0;
        while (p1 != null) {
            length1++;
            p1 = p1.next;
        }

        //计算B链表的长度
        ListNode p2 = headB;
        int length2 = 0;
        while (p2 != null) {
            length2++;
            p2 = p2.next;
        }

        ListNode longNode = headA;
        ListNode shortNode = headB;
        int longLength = length1;
        int shortLength = length2;

        if (length1 < length2) {
            longLength = length2;
            shortLength = length1;
            longNode = headB;
            shortNode = headA;
        }

        int step = longLength - shortLength;
        ListNode shortP = shortNode;
        ListNode longP = longNode;
        while (step >= 0) {
            longP = longP.next;
            step--;
        }
        while (shortP != null && longP != null && shortP != longP) {
            longP = longP.next;
            shortP = shortP.next;
        }
        return shortP;

    }

}
